//正则表达式匹配
class Solution {
public:
    bool isMatch(string s, string p) 
    {
        int m = s.length(), n = p.length();
        vector<vector<bool>> dp(m+1, vector<bool>(n+1));
        dp[0][0] = true;
        // 初始化第一行
        for (int j = 2; j <= n; j++) 
        {
            dp[0][j] = dp[0][j-2] && p[j-1] == '*';
        }
        // 状态转移
        for (int i = 1; i <= m; i++) 
        {
            for (int j = 1; j <= n; j++) 
            {
                if (p[j-1] != '*') 
                {
                    dp[i][j] = dp[i-1][j-1] && 
                        (s[i-1] == p[j-1] || p[j-1] == '.');
                } else 
                {
                    dp[i][j] = dp[i][j-2] || 
                    (dp[i-1][j] && (s[i-1] == p[j-2] || p[j-2] == '.'));
                }
            }
        }
    return dp[m][n];
    }
};
//正数相加
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
    {
        ListNode* head=new ListNode(-1);
        ListNode* cur=head;
        int carry=0;
        while(l1 || l2)
        {
            int n1=l1==nullptr?0:l1->val;
            int n2=l2==nullptr?0:l2->val;
            int sum=n1+n2+carry;
            carry=sum/10;
            cur->next=new ListNode(sum%10);
            cur=cur->next;
            if(l1) l1=l1->next;
            if(l2) l2=l2->next;
        }
        if(carry)
        {
            cur->next=new ListNode(carry);
        }
        return head->next;
    }
};